package 程序员面试金典;

import java.util.HashSet;

/**
 * 面试题 02.01. 移除重复节点
 * 编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。
 *
 * 示例1:
 *
 *  输入：[1, 2, 3, 3, 2, 1]
 *  输出：[1, 2, 3]
 * 示例2:
 *
 *  输入：[1, 1, 1, 1, 2]
 *  输出：[1, 2]
 * 提示：
 *
 * 链表长度在[0, 20000]范围内。
 * 链表元素在[0, 20000]范围内。
 * 进阶：
 *
 * 如果不得使用临时缓冲区，该怎么解决？
 */
public class T02_01 {
    public ListNode removeDuplicateNodes(ListNode head) {

        //使用hashSet 记录 出现过的值
        HashSet<Integer> hashSet = new HashSet<>();
        if (head==null){
            return head;
        }

        ListNode listNode = new ListNode(-1);
        listNode.next = head;  //虚拟的头节点方便删除

        while (listNode.next!=null){

            if (hashSet.contains(listNode.val)){ //存在过的元素 删除该节点
                listNode.next = listNode.next.next;
            }else {
                hashSet.add(listNode.next.val);
                listNode = listNode.next;
            }

        }

        return head;


    }

    //链表的定义
    static class ListNode{
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }
}
